package com.nowcoder.code.hjnc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class NC93 {

    public static void main(String[] args) {
        int[][] ins = {{1,1,1},{1,2,2},{2,1},{1,3,3},{2,2},{1,4,4},{2,1},{2,3},{2,4}};
        int[] ints = new NC93().LRU(ins, 3);

        System.out.println(Arrays.toString(ints));
    }

    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */

    HashMap<Integer, Node> map = new HashMap<>();
    int size = 0;
    Node head;
    Node end;

    ArrayList<Integer> list = new ArrayList<>();

    public int[] LRU(int[][] operators, int k) {
        head = new Node();
        end = new Node();
        head.next = end;
        end.prev = head;

        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) {
                if (map.containsKey(operators[i][1])) {
                    Node node = map.get(operators[i][1]);
                    node.next.prev = node.prev;
                    node.prev.next = node.next;

                    end.prev.next = node;
                    node.prev = end.prev;
                    node.next = end;
                    end.prev = node;
                    node.val = operators[i][2];


                } else {
                    Node node = new Node();
                    node.key = operators[i][1];
                    node.val = operators[i][2];
                    node.prev = end.prev;
                    node.next = end;
                    end.prev.next = node;
                    end.prev=node;


                    if (size == k) {
                        Node rm = head.next;
                        head.next = rm.next;
                        head.next.prev = head;
                        map.remove(rm.key);
                        size--;
                    }
                    size++;
                    map.put(node.key, node);
                }
            } else {
                Node node = map.get(operators[i][1]);
                if (node == null) {
                    list.add(-1);
                    continue;
                }
                list.add(node.val);
                node.next.prev = node.prev;
                node.prev.next = node.next;

                end.prev.next = node;
                node.prev = end.prev;
                node.next = end;
                end.prev = node;
            }
        }

        int[] results = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            results[i] = list.get(i);
        }
        return results;
    }

    private static class Node {
        int key;
        int val;
        Node prev;
        Node next;
    }

}
